1. Technical Field
The present invention relates to electronic design automation and more particularly to delay-optimizing technology-mapping in the high-level synthesis of digital systems.
2. Description of the Prior Art
High-level synthesis (HLS) automates certain sub tasks of a digital system design in an electronic design automation (EDA) system. A system architect begins by designing and validating an overall algorithm to be implemented, e.g., using xe2x80x9cCxe2x80x9d, xe2x80x9cCxe2x80x9d++, a specialized language, or a capture system. The resulting architectural specification is partitioned into boards, chips, and blocks. Each block is a single process having its own control flow. There are usually tens to hundreds of such blocks in a modem large-scale chip design. Typical blocks represent whole filters, queues, pipeline stages, etc. Once a chip has been partitioned into its constituent blocks, any needed communication protocols have to be constructed. Such protocols depend on cycle-by-cycle communication between blocks.
So-called xe2x80x9cschedulingxe2x80x9d and xe2x80x9callocationxe2x80x9d are applied one block at a time. Scheduling assigns operations such as additions and multiplications to states of a finite-state machine (FSM). Such FSM describes a control flow in an algorithm performed by a block being synthesized. Some operations are locked into particular states, and represent communication with other blocks. These input/output operations cannot be moved, or rescheduled, from one state to another, because to do so would probably upset the block-to-block communication protocol.
However, some other operations can be moved from one state to another. Moving operations from states that have many operations to states that have few allows hardware resources to be more evenly shared among operations. Timing problems can sometimes be resolved by moving certain operations from states in which operation delays cause timing problems into states in which such problems don""t exist.
Allocation maps the operations of a scheduled FM to particular hardware resources. For example, three addition operations can be scheduled to only require a single adder. An appropriate adder is constructed, and the operations are assigned to the adder in a schedule. But complications can arise when more than one hardware resource of a given bit-width and function is needed. And so which resource to use for each operation must be decided. Considerations include multiplexing cost, the creation of false timing paths, register assignment, and even using large resources for small operations. Hardware resources can be used for multiple functions. Calculating a minimum set of resources for an entire process is difficult but rewarding. Sometimes alternative implementations will be possible. It is often possible to choose implementations that meet the overall timing resources (abstract functions) to gate level implementations.
Allocation includes calculating a register set and assigning data to registers for use in later states. For example, temporary variables are used to store intermediate results in a larger calculation. But the contents of such temporary variables could share a common register in different states. The contents are only needed in one state each. So it is possible to save on hardware by assigning the data that needs to be stored to such storage elements. But register and storage allocations can be complicated if data values can form mutually exclusive sets or can share storage. Data values often drive functional resources, and in turn are often produced by functional resources. A good assignment of data to storage will complex by the fact that there are many ways to map an individual Boolean gate, and each way has its own unique advantages.
Technology-independent, or Boolean, optimization follow scheduling and allocation. The circuit design comprises generic AND and OR gates connected in a netlist. Technology-independent optimization minimizes the number of literals in the netlist. An abstraction of Boolean gates lends itself to a highly mathematical treatment based on Boolean arithmatic. For example, the Boolean identity AB+AC=A(B+C) can be used to reduce the corresponding gate network. Technology mapping follows Boolean optimization, the abstract Boolean gates of the circuit are mapped to standard cells from a technology library. Standard library cells include simple AND, OR, or NOT functions, and much more complex functions. For example, full adders, and-or-invert gates, and multiplexers. Technology-library gates are available in a variety of drive strengths, delays, input loadings, etc. Technology mapping is made more complex by the fact that there are many ways to map an individual Boolean gate, and each way has its own unique advantages.
Technology mapping can sometimes be avoided by constructing custom gate layouts for the gates of a circuit, instead of selecting cells from a library of preconstructed and precharacterized cells. But this method is not commonly associated with automatic synthesis.
The layout tasks of cell placement and net routing follow technology mapping, the physical position of each cell on the chip is established (placement), and the nets necessary to interconnect the cells are laid out (routing). In application service provider 104, the design intellectual property is downloaded to the user for placing and routing.
An abstract Boolean netlist is technology-mapped to standard-cell library elements, and involves matching and selection. A gate or a small collection of gates in a netlist is tested for logical equivalence to an element of the technology library to find a match. Matching can be done on an individual gate basis, or on a collection of gates. For example, there might be an AND-OR-INVERT gate in a technology library that would be capable of implementing an entire example netlist. Matching can also be partial, as in the case of a three-input gate in a technology library that could be used to implement a two-input gate in a netlist by tying one of its inputs to a constant.
Given that each of the gates of a netlist can be implemented by one or more gates from a technology library, one of the matches must be selected. Such a selection must xe2x80x9ccoverxe2x80x9d the netlist. Each gate of the netlist must have a selected matching element. The circuit derived by replacing each abstract gate with its selected matching technology library gate must be logically equivalent to the original circuit. The derived circuit should minimize overall area, delay, and/or other properties, while obeying any design rules imposed by the library or the designer. The technology mapping phase is completed when all the abstract gates of a netlist have been replaced by equivalent technology library elements.
A final phase of logic synthesis is an optional iterative improvement. In this step, the entire netlist is optimized, a few gates at a time, by making local changes. One way to do this is represented by,
repeat {
choose a gate G
try alternative mappings of G, keeping any improvement
} until no further improvements can be found.
Each iterative improvement step can be slow, because a large number of alternative selections could be constructed, even for a small circuit. For example, in a circuit that has ten gates, each of which have ten possible technology matches. If all combinations are considered, there would be 1,010 possible implementations of the circuit. Depending on the circuit""s topology and the properties of the library elements, the effects of alternative mappings can interact. Each gate might have to be visited many times before no further improvement could be obtained.
Attempts at iterative improvements can also be unreliable, as a good circuit may never be found. A local minima can occur, in which counter-intuitive xe2x80x9cuphill movesxe2x80x9d must be made that degrade the circuit in order to enable other changes that will have a desirable overall effect. If the uphill moves needed are outside the iterative improvement algorithm""s horizon, the process gets stuck and cannot improve the circuit beyond a certain point even though a better solution might exist.
There are conventional ways to address the local minima problem, e.g., simulated annealing and randomized search. But the prior art techniques are too slow. What is needed is a method that makes a good initial selection, so iterative improvement cycles can be skipped altogether.
FIG. 1 refers to a general graph-matching problem 100, where there are two graphs, a pattern graph 102 G1=(v1, e1), and a target graph 104 G2=(v2, e2). The goal is to find a one-to-one mapping 106 from the elements of the pattern to the elements of the target graph. A subgraph of G2, defined by the matched nodes, must be isomorphic to G1. An example of such a matching is shown here, with the matched nodes and arcs shown in an envelope 108.
FIG. 2 illustrates a circuit 202 and its corresponding bipartite graph representation 204. In essence, the gates are converted to nodes, and the interconnects to arcs. The particular technology-mapping matching problem differs from the more general problem of matching. Graphs extracted for circuits are directed bipartite graphs, e.g., G=(V1, v2, e), where edges in xe2x80x9cexe2x80x9d connect elements of v1 to elements of v2, but never elements of v1 to v1 or elements of v2 to v2. The edges are ordered pairs, e.g., they have a direction. The nodes in v2 represent gates, and the nodes in v1 represent circuit nets. Graph matching for bipartite directed graphs is such that a net node can only map to a net node, a gate node can only map to a gate node, and isomorphism is used to preserve the direction of edges. The nodes in bipartite graph representation 204 that represent gates have types, e.g., AND ({circumflex over ( )}), OR (v), and NOT (!). These form part of the isomorphism construction. A node of type X in G1 is mapped to a node of type X in G2.
The prior art usually only matches trees. Directed acyclic graphs (DAG""s) can be used to represent some types of multiple-output gates, and so combinational logic circuits can be represented by a DAG. That is, as long as they contain no cycles. DAG""s must also be well-formed and avoid including cyclic false paths.
FIG. 3 illustrates a first step in technology mapping which is to partition a network graph 302 into a collection of trees 304-308 or DAG""s. Each tree 304-308 can then be worked on as an individual mapping problem. The simplest formulation is to use trees, but an extension to DAG""s would not be difficult. In general, the trees are defined so that their roots and leaves are all net nodes, as opposed to gate nodes. Root and leaf nodes are duplicated as many times as necessary, otherwise they will have to be shared between trees. The trees 304-308 should be as large as possible, e.g., maximal trees. In any extension to DAG""s, the number of output terminals of a DAG must be limited to two, or other small number. Otherwise, the matching computations get too complex.
A typical technology library includes a number of cells that represent primitive elements. Combinational cells in the library have Boolean functions. A selection of bipartite directed a graph representations is constructed for each cell. Each of these graphs is associated with the cell""s Boolean function expressed in a small primitive-type alphabet. One convenient alphabet of primitive type is that of two-input NAND gates and inverters. Each cell of the library is described by a tree (or DAG) comprising only net nodes, two-input NAND nodes, and NOT nodes. The exact alphabet chosen is not crucial as long as it is relatively simple, and it is logically complete. All Boolean functions can be expressed as networks comprising only units of the alphabet.
Such a decomposed library is shown in FIG. 4. Cell names are listed in the left column. The middle column lists the corresponding Boolean functions. And each cell is represented by one or more pattern trees as shown in the right column.
Any circuit designs submitted to technology mapping processes are usually represented as networks of simple gates, e.g. NAND, AND, NOR, OR, XOR, and NOT. Each network can be converted to a functionally equivalent network using only the library-tree gate types and fan-ins. For the example library of FIG. 4, the circuit would be converted into an equivalent circuit comprising only inverters and two-input NAND gates. It is then mapped into a bipartite directed graph representation, e.g., in the same style as the library-pattern graphs. After that, it is possible to do the graph matching. Both the library cells and the circuit to be mapped are represented using the same graph formalism.
The trees of a circuit are individual matching problems. Any matching results are preferably encoded by attaching a list of matching pattern trees to each net node N. Such list represents a set of pattern trees whose roots match N. The following pseudocode implements such, and refers to this list as matchings(N),
There are a number of ways to implement a tree-matching test with pattern-matching algorithms. For example, a recursive algorithm can recognize that a circuit tree matches a pattern tree if the roots match, and all the circuit-tree subtrees map to all the pattern-tree subtrees in matching pairs. The subtree mapping must be one-to-one circuit subtrees to pattern subtrees, each subtree of a circuit tree must map to exactly one subtree of a pattern tree. Every subtree of the pattern tree must be mapped to by some subtree of the circuit tree, e.g., xe2x80x9contoxe2x80x9d mapping. Without this, more than one subtree of the circuit tree might b e mapped to a single subtree of the pattern tree, or fail to map to some subtree of the pattern at all.
If one matching of subtree to subtree fails, another might succeed. The trees might be asymmetric. All permutations of the ordered list of subtrees of the pattern tree are tested against the ordered list of subtrees of the circuit tree. If all permutations fail, the match attempt as a whole is abandoned. A match is found if any permutation succeeds.
The following pseudocode implements a matching algorithm. All of the named nodes are net nodes. The gate nodes are net node drivers. A list xe2x80x9cUxe2x80x9d referred to in the if statement is a list of drivers of drivers of the net N, e.g., drivers of gate G that drive net node N. xe2x80x9cMxe2x80x9d is a net node of the pattern tree, and xe2x80x9cNxe2x80x9d is a net node of the circuit tree.
In this form, such algorithm becomes increasingly expensive as the fan-in of the technology library cells increase. The complexity is exponential. The algorithm can be sped up, but this one is fast enough for most current technology libraries.
The matching step produces a one-to-many mapping from the net nodes of the circuit to root nodes of pattern trees. Such mapping candidates are functions that take a net node as their argument, and return a list of pattern trees. An implementation of the circuit becomes a set of net nodes, for which one member of the candidate set is selected. The set of net nodes chosen will usually be smaller than the entire set of net nodes because some net nodes will be xe2x80x9cburiedxe2x80x9d inside patterns that have interior net nodes.
FIG. 5 shows a circuit tree on the right, and the only two pattern trees on the left that are needed to match every part of the circuit tree. Each of the possible matches of a pattern tree to a piece of the circuit tree net nodes is shown as a dashed line. Thus the entire circuit can be xe2x80x9ccoveredxe2x80x9d with as few as four gates if a proper subset of six matchings shown is chosen. In other words, the circuit tree can be decomposed into four constituent gate types. Subsets of the six matchings shown could produce redundant or incomplete coverings. The challenge is to select a subset of the matchings that minimizes delay and redundancy, and that covers.
Prior art devices and methods are unsatisfactory when it comes to covering while minimizing delay and keeping redundancy down.
Briefly, a delay-optimizing technology-mapping process embodiment of the present invention for an electronic design automation system selects the best combination of library devices to use in a forward and a backward sweep of circuit trees representing a design. A technology selection process in an electronic design automation system comprises the steps of partitioning an original circuit design into a set of corresponding logic trees. Then, ordering the set of corresponding logic trees into an ordered linear list such that each tree-T that drives another ordered tree precedes the other ordered tree, and such that each ordered tree that drives the tree-T precedes the tree-T. Next, sweeping forward in the id ordered linear list while computing a set of Pareto-optimal load/arrival curves for each of a plurality of net nodes that match a technology-library element. And, sweeping backward in the ordered linear list while using the set of Pareto-optimal load/arrival curves for each of the net nodes and a capacitive load to select a best one of the technology-library elements with a shortest signal arrival time. Wherein, only those net nodes that correspond to gate inputs are considered, and any capacitive loads are predetermined.